1. Field of the Invention
The present invention relates generally to a decoding apparatus and method, and in particular, to a turbo decoding apparatus and method.
2. Description of the Related Art
As communication systems develop and mobile communication is popularized, there is an increasing demand for minimizing errors that occur in a communication process. Accordingly, researchers studying channel codes have attempted to find codes having performance approaching Shannon's limit. To date, different high-performance codes, such as turbo codes, have been proposed, which are generated by highly complex coding rules, but there is still difficulty in providing a low-complexity decoder capable of effectively decoding these codes.
A conventional encoding apparatus and a decoding apparatus that use the normal turbo codes (or Binary Turbo Codes) are illustrated in FIG. 1.
Referring to FIG. 1, generally, a turbo coding apparatus 110 includes two encoders 121 and 123, a puncturer 140, and an interleaver 130 for connecting the encoders 121 and 123. The turbo coding apparatus 110 receives an input information bit stream un and outputs one output bit stream vns. In addition, the turbo coding apparatus 110 inputs the input information bit stream un to the first encoder (ENC 1) 121, and obtains a first parity bit stream. The input information bit stream un is input to the interleaver 130 having the same size as a length of the input information bit stream un, and interleaved according to a predetermined pattern. The interleaved input information bit stream is input to the second encoder (ENC 2) 123 where a second parity bit is obtained. The output of the turbo coding apparatus 110 has dual-parity information due to the output of the first encoder 121 and also due to the output modified by the interleaver 130. The outputs can undergo puncturing by the puncturer 140 to obtain a code rate desired by the turbo coder. For example, in order to set the code rate to ½, the puncturer 140 can perform puncturing so that the outputs from the two encoders are alternately output. The parity bit vnp finally obtained through the puncturing is transmitted through a transmission channel with the output bit stream vns.
The coding method for the turbo codes is called “a coding method for parallel concatenated codes,” because the two encoders are applied to a set of the same input sequences though they are different in arrangement.
A codeword coded by the turbo coding apparatus 110 is subjected to decoding by a decoding apparatus 150 for turbo codes. Generally, the decoding apparatus 150 uses a Soft Input Soft Output (SISO) decoder that uses a Maximum A Posteriori (MAP) algorithm to generate information on each bit. Further, to improve decoding performance, the decoding apparatus 150 uses iterative decoding (Iteration).
Referring again to FIG. 1, the decoding apparatus 150 for turbo codes includes two decoders (DEC 1 and DEC2) 161 and 163, interleavers 162, 164, and 165, and a de-puncturer 170. When information bits yns and parity bits ynp are defined as a signal that a codeword of the turbo coder has passed through a channel, yns is a signal that the information bits have passed through the channel, and ynp is a signal that the parity bits have passed through the channel. The decoders 161 and 163 each receive, as priori information, received signals yns and ynp, and extrinsic bits, or information output in the previous decoding process, and generate Log likelihood Ratio (LLR) Le by performing decoding thereon.
Extrinsic information included in the LLR improves decoding reliability, as it is priori information of the next decoding stage. This is called a “MAP algorithm”. An example of the MAP algorithm is illustrated in FIG. 2, which will be described in more detail below. Commonly, the MAP algorithm performs 8-iteration decoding to decrease BER, thereby increasing decoding performance.
FIG. 2 illustrates a detailed structure of a decoder 200 in an ith iteration. Referring to FIG. 2, the decoder 200 receives information bits ys, parity bits yp, and extrinsic bits Le, or an output value in an (i−1)th iteration, and generates an LLR for each bit.
Extrinsic information included in the LLR improves decoding reliability, as it is priori information of the next decoding stage in an (i+1)th iteration. Further, the extrinsic information should be stored in a memory for the next decoding.
FIG. 3 illustrates an encoding apparatus and a decoding apparatus for Non-Binary Turbo Codes. Referring to FIG. 3, the Non-Binary Turbo Codes are similar to the Binary Turbo Codes illustrated in FIG. 1 in that an encoder 310 includes two encoders 321 and 323, a puncturer 340, and an interleaver 330 connecting the two encoders 321 and 323, but are different in that the input codes are Binary Turbo Codes. Referring to FIG. 3, the Non-Binary Turbo Codes are different in that encoding is performed as in the Binary case but the number of encoder information symbols received at a time is expressed as un=(un0, un1) of 2 bits.
Similarly, referring to FIG. 4, which is a diagram illustrating an example of a MAP algorithm in Non-Binary Turbo Codes, information symbols yn=(yns0, yns1), parity symbols ynp, and extrinsic symbols Le=(LeA LeB LeC) needed in a decoder 410 are also input at a time.
As to the number of encoder input bits, because k bits, not 1 bit, are received as inputs, and decoding is performed in units of 2k-ary symbols, not in a bit-by-bit calculation. For example, for binary turbo codes with 2 simultaneous input bits (k=2), an LLR value is calculated with 4-ary symbols of (1,1), (1,−1), (−1,1), and (−1,−1). The LLR calculation is a probability ratio calculation, and because one of four combinations is regarded as a reference, a total of (2k−1) LLR values are needed, so 3 LLR values are needed for the above binary turbo codes.
Therefore, as (2k−1) extrinsic information values per k input bits are needed for non-binary decoding, the non-binary turbo codes are higher in terms of an extrinsic memory size than the binary turbo codes by (2k−1)/k.
Binary turbo codes with k=2 are higher by 1.5 times in terms of the memory than the binary case.
Referring to Table 1, the memory for extrinsic information occupies 43% of a total decoder area.
TABLE 1AreaGate CountsPercentageDecoder logic22,86717%Forward/Backward Metric Memory11,0098%Extrinsic Information Memory59,31043%Memory for Received Signal29,44021%Interleaver Memory15,01311%Total137,639100%
Because the memory for storing extrinsic information occupies a considerable part of the decoder, the size of the memory is very significant in determining the size of the decoder. Accordingly, there is a need to reduce a size of the memory.